package graph.weighted.connectedComponent;

import java.util.ArrayList;
import java.util.Arrays;

import graph.weighted.CandyWeightedGraph;
import queue.CandyLoopQueue;

/**
 * 
 * @Title: CandyConnectedComponent.java 
 * @Package graph.bfs.connectedComponent 
 * @Description: 用BFS求图的连通分量
 * @author CandyWall   
 * @date 2021年1月17日 上午11:54:41 
 * @version V1.0
 */
public class CandyConnectedComponent {
    private CandyWeightedGraph graph;
    private int[] visited;
    private int connectedComponentCount;
    public CandyConnectedComponent(CandyWeightedGraph graph) {
        this.graph = graph;
        visited = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = -1;
        }
        bfs();
    }
    
    public void bfs() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(visited[v] == -1) {
                bfs(v, connectedComponentCount);
                connectedComponentCount++;
            }
        }
    }

    /**
     * 判断两个顶点是否连接，即是否在同一个连通分量中
     * @param v
     * @param w
     * @return
     */
    public boolean isConnected(int v, int w) {
        graph.validateVertex(v);
        graph.validateVertex(w);
        return visited[v] == visited[w];
    }
    
    /**
     * 获取所有的连通分量，每个集合中保存相应连通分量中的元素
     */
    public ArrayList<Integer>[] getConnectedComponents() {
        ArrayList<Integer>[] res = new ArrayList[connectedComponentCount];
        for(int i = 0; i < connectedComponentCount; i++) {
            res[i] = new ArrayList<Integer>();
        }
        for(int v = 0; v < visited.length; v++) {
            res[visited[v]].add(v);
        }
        return res;
    }
    
    private void bfs(int s, int connectedComponentId) {
        CandyLoopQueue<Integer> queue = new CandyLoopQueue<>();
        queue.enqueue(s);
        visited[s] = connectedComponentId;
        while(!queue.isEmpty()) {
            int v = queue.dequeue();
            for(int w : graph.adjacentVertexes(v)) {
                if(visited[w] == -1) {
                    queue.enqueue(w);
                    visited[w] = connectedComponentId;
                }
            }
        }
    }
    
    public int getConnectedComponentCount() {
        return connectedComponentCount;
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph = new CandyWeightedGraph("testData/graph/graph.txt");
        CandyConnectedComponent cc = new CandyConnectedComponent(graph);
        System.out.println("连通分量的个数为：" + cc.getConnectedComponentCount());
        System.out.print("连通分量为：");
        System.out.println(Arrays.toString(cc.getConnectedComponents()));
    }
}